package com.zzg.datastructure.sort;

import java.util.Arrays;

/**
 * @Author zhengzg
 * @Date 2022-08-23
 * @Version v1.0
 * 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{-1, 9, 0, 1, 1, -2, 6, 3, -999};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 快速排序，Arrays.sort()底层用的也是，可以参照代码
     *
     * @param arr   传入的数组
     * @param left  0
     * @param right arr.length - 1
     */
    private static void quickSort(int[] arr, int left, int right) {
        // 创建扫描指针
        int leftIndex = left;
        int rightIndex = right;

        // 获取中轴值
        int pivot = arr[(leftIndex + rightIndex) / 2];

        // 临时变量
        int temp = 0;

        // while循环的目的是让比pivot值小放在左边，比pivot值大的放在右边
        while (leftIndex < rightIndex) {
            // 在pivot的左边一直找，找到大于等于pivot的值，退出
            while (arr[leftIndex] < pivot) {
                leftIndex++;
            }
            // 在pivot的右边一直找，找到小于等于pivot的值，退出
            while (arr[rightIndex] > pivot) {
                rightIndex--;
            }
            // 如果leftIndex >= rightIndex 说明pivot左右两侧的值均已排好
            if (leftIndex >= rightIndex) {
                break;
            }

            // 交换
            temp = arr[leftIndex];
            arr[leftIndex] = arr[rightIndex];
            arr[rightIndex] = temp;

            /*
             * 下面两个操作可以防止死循环，如果不增加索引，两个位置的数据就会无限交换导致死循环
             */
            // 如果交换完成后，发现这个arr[leftIndex] == pivot rightIndex--，前移
            if (arr[leftIndex] == pivot) {
                rightIndex--;
            }

            // 如果交换完成后，发现这个arr[rightIndex] == pivot leftIndex++，后移
            if (arr[rightIndex] == pivot) {
                leftIndex++;
            }
        }
        // 如果leftIndex == rightIndex 必须leftIndex++，rightIndex--，否则栈溢出
        if (leftIndex == rightIndex) {
            leftIndex++;
            rightIndex--;
        }

        // 向左递归
        if (left < rightIndex) {
            quickSort(arr, left, rightIndex);
        }

        // 向右递归
        if (right > leftIndex) {
            quickSort(arr, leftIndex, right);
        }
    }
}
